package datastructures;
//用递归树来求解时间复杂度
public class RecursionTree {


    public static void main(String[] args) {
        int[]a = {1, 2, 3, 4};
        printPermutations(a, 4, 4);
    }

    //1. 分析全排列的时间复杂度
    // k 表示要处理的子数组的数据个数
    public static void printPermutations(int[] data, int n, int k) {
        if (k == 1) {
            for (int i = 0; i < n; ++i) {
                System.out.print(data[i] + " ");
            }
            System.out.println();
        }

        for (int i = 0; i < k; ++i) {
            int tmp = data[i];
            data[i] = data[k-1];
            data[k-1] = tmp;

            printPermutations(data, n, k - 1);

            tmp = data[i];
            data[i] = data[k-1];
            data[k-1] = tmp;
        }
    }

    //2 题目2
    // 1 个细胞的生命周期是 3 小时，1 小时分裂一次。求 n 小时后，容器内有多少细胞？
    // 请你用已经学过的递归时间复杂度的分析方法，分析一下这个递归问题的时间复杂度。
//    思路：f(n) = 2 * f(n-1) - 【n时刻点死掉的细胞数量】
//    而在【n时刻点死掉的细胞数量】就是【n-3时刻点新分裂的细胞数量】;【n-3时刻点新分裂的细胞数量】就是【n-4时刻点的细胞数总数】，即f(n-4)
//
//    故递推公式：f(n) = 2 * f(n-1) - f(n-4)


}
